package 打家劫舍III;

import java.util.HashMap;

/**
 * @author: AirMan
 * @date: 2025/5/13 11:43
 * @description:
 */
public class Solution2 {
    public int rob(TreeNode root) {
        // 记忆化递归计算，如果某个值以及计算过了，就将他存入到set中
        // 一定要选择后序遍历，因为我们需要根据递归函数的返回值确定下一次的计算
        HashMap<TreeNode, Integer> map = new HashMap<>();
        return recursion(root, map);
    }

    public int recursion(TreeNode root, HashMap<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        if (map.containsKey(root)) return map.get(root);
        // 偷父节点
        int val1 = root.val;
        // left
        if (root.left != null) val1 += recursion(root.left.left, map) + recursion(root.left.right, map);
        // right
        if (root.right != null) val1 += recursion(root.right.left, map) + recursion(root.right.right, map);
        // 不偷父节点
        int val2 = recursion(root.left, map) + recursion(root.right, map);
        int nowMax = Math.max(val1, val2);
        map.put(root, nowMax);
        return nowMax;
    }
}
